class Solution {
public:
    string longestPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.length() == 0) {
            return string("");
        }
        int start = -1;
        int end = -1;
        int n = s.length();

        for (int i = 0; i < n; ++i) {
            int l = i;
            int r = i;
            while (l >= 0 && r < n && s[l] == s[r]) {
                --l;
                ++r;
            }
            ++l;
            --r;
            if (start < 0 || r - l  + 1 > end - start + 1) {
                start = l;
                end = r;
            }

            l = i;
            r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) {
                --l;
                ++r;
            }
            ++l;
            --r;
            if (start < 0 || r - l + 1 > end - start + 1) {
                start = l;
                end  = r;
            }
        }
        return s.substr(start, end - start + 1);
    }
};
